1. Field of the Invention
The present invention relates to an encryption apparatus, decryption apparatus, key generation apparatus, program, and method which are based on a public-key cryptosystem using algebraic surfaces.
2. Description of the Related Art
In a networked society, people communicate with each other by transmitting a large amount of information such as e-mail on networks. In such a networked society, cryptographic technologies are widely used as a means for protecting confidentiality and authenticity.
Cryptographic technologies can be roughly classified into secret-key cryptographic technology and public-key cryptographic technology. Secret-key cryptography is a cryptographic scheme based on a data shuffling algorithm, which enables fast encryption/decryption, but allows secured communication and authenticated communication only between two persons who have a secret key.
For this reason, secret-key cryptography is mainly used to encrypt information which needs to be decrypted in real time upon reception, such as a pay digital broadcast. In this case, a decryption key for the pay digital broadcast is distributed to only broadcast subscribers by using a key distribution system called a conditional access system.
Public-key cryptography is a cryptographic scheme based on a mathematical algorithm, which is slower in encryption/decryption than secret-key cryptography, but has the advantage of allowing secured communication and authenticated communication without requiring key sharing in advance. More specifically, public-key cryptography realizes secured communication by performing cryptographic processing using receiver's public key and allows a given user to perform authentication communication by applying a digital signature using his/her private key.
On network shops and bank and securities company online sites established on the Internet, public-key cryptography is often used to protect customer information such as credit card numbers and addresses from eavesdropping. This is because, an encryption key for encrypting customer information cannot be shared in some cases, and hence secret-key cryptography is unsuitable for such cases.
Typical public-key cryptography includes RSA cryptography and elliptic curve cryptography. RSA cryptography uses, as a basis for security, the difficulty of prime factorization, and uses exponential remainder computation as encryption computation. Elliptic curve cryptography uses, as a basis for security, the difficulty of the discrete logarithm problem on elliptic curves, and uses computation of points on elliptic curves for encryption computation.
With regard to this public-key cryptography, although decryption methods for specific keys (public keys) have been proposed, no general decryption method has been known. Therefore, no serious problem has been found in security so far except for the decryption method using a quantum computer (to be described later).
Other public-key cryptography includes knapsack cryptography and multivariate polynomial type cryptography. Knapsack cryptography uses, as a basis for security, the difficulty of the knapsack problem as an NP problem. Multivariate polynomial type cryptography is constructed by using the theory of field extensions and uses, as a basis for security, the solution problem of simultaneous equations.
With regard to knapsack cryptography, however, decoding methods for most of the implementation forms are known, and hence problems arise in terms of security. With regard to multivariate polynomial type cryptography, a powerful decoding method is known. It is also known that this decoding method can be avoided by increasing the key size. According to multivariate polynomial type cryptography, however, the key size required to avoid the decoding method becomes too large, and hence problems have begun to arise.
On the other hand, if a quantum computer is developed, even an RSA cipher and elliptic curve cipher may be decrypted. A quantum computer is a computer which can execute massively parallel calculations by using a physical phenomenon known as entanglement in the quantum theory on the basis of a principle different from that of current computers. Although a quantum computer is a hypothetical computer whose operation has been checked only at the experimental level so far, research and development have progressed to realize it. In 1994, Shor demonstrated that the use of a quantum computer could enable an algorithm which efficiently solved the prime factorization and discrete logarithm problems. That is, the realization of a quantum computer makes it possible to decrypt an RSA cipher based on prime factorization and an elliptic curve cipher based on the discrete logarithm problem.
Under the circumstances, public-key cryptography has recently been studied, which will remain secure even if a quantum computer is realized. As an example of cryptography which is robust against a quantum computer, quantum public-key cryptography can be presented. See, for example, reference (T. Okamoto, K. Tanaka and S. Uchiyama: “Quantum Public-Key Cryptosystems”, Advances in Cryptology—CRYPTO2000, Lecture Notes in Computer Science, vol. 1880, pp. 147-165, Springer-Verlag, 2000.) According to quantum public-key cryptography, a quantum computer is actively used to generate keys that form a robust knapsack cipher which cannot be generated in reality by current computers. Quantum public-key cryptography can therefore create a robust knapsack cipher which cannot be decrypted even by a quantum computer.
Quantum public-key cryptography is, however, a scheme which cannot be used at present because it is impossible for current computers to generate keys for the cryptography. On the other hand, multivariate polynomial type cryptography is currently feasible public-key cryptography, which is regarded to be difficult to decrypt. Multivariate polynomial type cryptography, however, requires a very large key size for security against current computers, and hence its practical application is now in question.
In addition, public-key cryptography requires a larger circuit size and longer processing time than secret-key cryptography. For this reason, public-key cryptography cannot be realized in a low-power environment like that for mobile terminals and the like, or even if realized, requires a long wait time. Demands have therefore arisen for public-key cryptography which can be realized even in a low-power environment.
In general, public-key cryptography finds in advance a problem that is difficult to calculate, e.g., a prime factorization problem or discrete logarithm problem, and is designed to force a person who tries to decrypt a ciphertext without knowing a private key to perform operation equivalent to solving the problem that is difficult to calculate.
Even if, however, a problem that is difficult to calculate is found, it does not mean that public-key cryptography whose security is based on the problem can be easily created. This is because, using an excessively difficult problem as a basis for security makes a problem of generating a key difficult, resulting in incapability of generating a key. On the other hand, if a problem is made easier to the extent that a key can be generated, decryption is also made easier.
In order to create public-key cryptography, therefore, it is necessary to find a problem that is difficult to calculate and to convert the problem so as to achieve a delicate balance between making it easy to the extent that a key can be generated and not making it easy to the extent that any person can perform decryption without knowing a private key. Such a conversion of the problem demands high creativity. In practice, since it is very difficult to change such a problem, only a few kind of public-key cryptography have been proposed until now.
As described above, it is required for public-key cryptography to be difficult to solve even by a quantum computer and be realized even by current computers. In addition, public-key cryptography is required to be realized even in a low-power environment.